1. Field of the Invention
The invention relates generally to communication coding, and it relates, in particular, to coding of control blocks in order to minimize delay between reception and transmission at a node.
2. Prior Art
One popular type of local network communication system is a token ring, the structure of which is illustrated in FIG. 1. Further details on token rings are available in an article by N. C. Strole, entitled "A Local Communication Network Based on Interconnected Token-Access Rings: A Tutorial", appearing in the IBM Journal of Research and Development, volume 27, 1983 at pages 481-496. The token ring consists of multiple nodes 12, 14, 16 and 18 in the example, although rings of up to several hundred nodes are typically used. In the general case, each node is capable of receiving and sending messages to and from every other node on the ring. The nodes are connected by a uni-directional transmission line 20 that, as the name implies, forms a ring that closes on itself. The nodes are relatively independent of each other and, with the exception of a monitor node 12, are functionally equivalent. The monitor node 12 does not directly control the other nodes 14, 16 and 18, but performs the necessarily centralized tasks of timing synchronization and monitoring of the health of the ring. Data is transmitted between nodes in the form of packets having the format illustrated in FIG. 2. The packet consists of a header 22 which indicates to a receiving node that a packet is arriving, provides the information as to which node the packet is intended, synchronizes the clocks of the receiving node and provides some information as to the format of the packet. Following the header is the data stream 24 consisting of a series of blocks of data D.sub.1, D.sub.2, . . . D.sub.N. The length N of the data stream 24 can be any value up to a predetermined maximum and is not defined in the header 22. Thus the packet can contain a short message, a long message, or possibly no message at all. Following the data stream 24 is a trailer 26 that defines the end of the packet and provides space for certain houskeeping information to be transmitted along with the message. Because the data in the data stream 24 can be any possible value but the trailer 26 must be distinguished from a block of data D.sub. N, it is necessary that the blocks D.sub.1, D.sub.2, . . . D.sub.N be encoded. For the purposes of this application, coding for 2 block implies that additional bits have been added to the block for transmission over and above the number of bits of information in the block. The extra bits can denote a class of information with the information bits defining the information once the class has been defined. A very simple example of coding for blocks of data consisting of eight-bit bytes of data would be to add a ninth bit which would indicate if that encoded block is a data byte or a control byte. Once a block has been detected with the ninth bit indicating a control block, a receiving node would know that the data stream 24 is completed and what is being received is the trailer 26. It should be noted that only the first block of the trailer needs to be internally denoted as a control block. The remaining blocks may be data blocks included within the trailer format. Similar coding is required to signal the start of a packet. Coding is used for many other purposes than differentiating data and control blocks. One important purpose is to transform data into a signal stream suitable for serial transmission in which there must be frequent transitions for clock recovery at the receiving end. It is also desirable that the transmitted code be DC balanced, that is, that over some length of transmission the number of zeroes equals the number of ones. As example of such a code is Manchester code in which for data a binary zero is represented by 01 and a binary one is represented by 10. Thus Manchester coded data is necessarily DC balanced and has a transition in every complementary bit pair. If Manchester code is received consisting of three consecutive zeroes or three consecutive ones, i.e. 000 or 111, the receiving node knows that the received code is not data but should instead be interpreted as control blocks. The DC balance of control blocks is accomplished by further constraints on the entire control block. Thus it is seen that coding can take a much more complex form than simply adding a bit to indicate an additional characteristic of the block. Manchester coding is simple but inefficient.
Since the data stream 24 is subdivided into data blocks D.sub.1, D.sub.2, . . . D.sub.N, the header 22 in the trailer 26 is also typically broken down into individual blocks of the same size. For token ring communication systems, the header 22 contains a token. If a node receives a packet with a free token, i.e. the token in the header 22 indicates that the packet is not being used for a message from some other node, the receiving node can take the token by changing its value in the header 22, retransmitting the header with the changed token value followed by the message which that node desires to transmit, and of course finishing the transmission with the trailer 26. If, however, the receiving node detects a busy token, i.e. the value of the token in the header 22 indicates that a message or data stream 24 follows in the packet, then the receiving node simply retransmits the packet onto the next code. For example, if the node 14 in FIG. 1 receives a packet with a free token and it wishes to transmit a message, it takes the token by changing its value in the header. The transmitting node also adds a destination and a source address to the header to indicate which of the nodes on the ring should receive the message and the sender of the message. The message is then transmitted as the data stream 24, followed by an appropriate trailer 26.
If the node 14 is sending the message to the node 18 which is two nodes away, then the packet first arives at the intermediate node 16. This node first receives the header 22 and determines that the token is busy so that it cannot transmit its message in this packet and simply remains in a retransmission mode. Furthermore, from the destination address, it discovers that the message is intended for another node and ignores the packet for its own use. Of course, the node 16 also retransmits the trailer 26 perhaps with some slight modifications for houskeeping chores. When the packet is received by the destination node 18, once again the busy token indicates that it cannot transmit its own message on this packet. However it determines from the destination address that it is the intended recipient of the message and accordingly copies the data stream 24. In a typical system, the receiving node 18 retransmits the data stream 24 intact so that the packet eventually arrives back at the originating node 14 which can thereby determine that the message has travelled around the ring. At that time, the originating node changes the token back to a free token and removes the addresses, the data D.sub.1, D.sub.2. . . D.sub.N in the data stream 24, and the trailer 26 from the packet. Repeating the process, some other node receiving this packet with a free token and wishing to transmit a message grabs the token.
It is to be understood that a packet can pass through a very large number of nodes between the originating and destination nodes. At each of these intermediate nodes, a node must read and decode the header 22 to determine its subsequent course of action. The delay involved in the processing of the header introduces two difficulties. First of all, any delay within the node is equivalent to lengthening the transmission line 20 with the result that this delay, multiplied by the number of nodes on the ring, slows down the throughput of the ring. It must be remembered that in a typical ring, there is only a single token for a single message so that the circulation time around the ring, including all the nodal delays, limits the ring throughput. Furthermore, during the time that any node is receiving, decoding and processing the header 22, the blocks of the packet continue to arrive. Therefore, buffer memories must be provided to store the received data until it is retransmitted. Thus complex processing of the header 22 entails not only complex processing circuitry, but also large amounts of buffer storage. An ideal situation would be if, immediately upon the reception of the beginning of the header 22, the decision could be reached that the token is busy so that the data stream 24 could be retransmitted immediately upon reception. A token constitutes only one bit of information, busy or free. However in general coding schemes, there is not one bit in the encoded word which would correspond to the one bit token. In conventional systems, the entire block containing the token needs to be received and then decoded before the value of the token can be determined. Even with these minimal restraints, a significant mimimum delay is introduced at each node and a corresponding amount of buffer memory needs to be provided.